package io.gitee.wiqer.simple;

import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.stream.Collectors;

public class SolutionNC156_FoundOnceNumber {
    public int foundOnceNumber(int[] arr, int k) {
        Arrays.sort(arr);
        for(int i = 0; i<arr.length-1; i++){
            if(arr[i]==arr[i+1]){
                i += k-1;
            }else{
                return arr[i];
            }

        }
        return arr[arr.length-1];
    }
    public int foundOnceNumber_BitOperation (int[] arr, int k) {
        // 每个二进制位求和，如果某个二进制位不能被k整除，那么只出现一次的那个数字在这个二进制位上为1。
        int[] binarySum = new int[32];
        for(int i = 0; i< 32; i++){//求每个二进制位的和
            int sum = 0;
            for(int num : arr){
                sum += (num >>i & 1);//依次右移num，同1相与，计算每一位上1的个数
            }
            binarySum[i] = sum;
        }
        int res = 0;
        for (int i = 0; i< 32; i++){
            if(binarySum[i]%k!=0){
                res += 1<<i;//左移恢复
            }
        }
        return res;
    }
    public int foundOnceNumber_HashMap (int[] arr, int k) {
        // write code here
        HashMap<Integer, Boolean> map = new HashMap<>();//key存数字，value表示是否出现过
        for(int num: arr){
            if(map.containsKey(num)){
                map.put(num, true);
            }else{
                map.put(num, false);
            }
        }
        Set<Integer> set = map.keySet();
        for(int num : set){
            if(map.get(num) == false){
                return num;
            }
        }
        return 0;
    }
    public int foundOnceNumber_ConcurrentSkipListMap (int[] arr, int k) {
        // write code here
        ConcurrentSkipListMap<Integer, Boolean> map = new ConcurrentSkipListMap<>();//key存数字，value表示是否出现过
        for(int num: arr){
            if(map.containsKey(num)){
                map.put(num, true);
            }else{
                map.put(num, false);
            }
        }
        List<Integer> list= map.entrySet().stream().filter(entry -> !entry.getValue()).map(entry -> entry.getKey()).collect(Collectors.toList());
        return list.get(0);
    }
}
